package leetcode.f1t100;

import java.util.*;

/**
 * 构造n个括号相互嵌套的所有场景
 * https://leetcode.com/problems/generate-parentheses/
 * @Author lichongxiao
 * @Date 2022/9/30 10:38
 */
public class Q22_GenerateParentheses {
    public List<String> generateParenthesis1(int n) {
        Map<Integer, Set<String>> cache = new HashMap<>();
        Set<String> ansSet = process(n,cache);
        List<String> ansList = new ArrayList<>();
        ansList.addAll(ansSet);
        return ansList;
    }

    private Set<String> process(int n, Map<Integer, Set<String>> cache){
        Set<String> ansSet = new HashSet<>();
        if(n == 1){
            ansSet.add("()");
            cache.put(n,ansSet);
            return ansSet;
        }
        if(n == 2){
            ansSet.add("()()");
            ansSet.add("(())");
            cache.put(n,ansSet);
            return ansSet;
        }
        for (int i = 1; i < n-1; i++) {
            Set<String> tempAnsSet1 = process(i,cache);
            Set<String> tempAnsSet2 = process(n-i,cache);
            for(String ans1 : tempAnsSet1){
                for(String ans2:tempAnsSet2){
                    ansSet.add(ans1+ans2);
                }
            }
        }
        Set<String> tempAnsSet3 = process(n-1,cache);
        for(String ans3 : tempAnsSet3){
            ansSet.add(ans3+"()");
            ansSet.add("()"+ans3);
            ansSet.add("("+ans3+")");
        }
        cache.put(n,ansSet);
        return ansSet;
    }

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        process(n,0,0,"",ans);
        return ans;
    }
    private void process(int n, int left, int right, String str, List<String> ans){
        if(str.length() == 2*n){
            ans.add(str);
            return;
        }
        if(left < n){
            process(n, left+1, right, str+"(", ans);
        }
        if(right < left){
            process(n, left, right+1, str+")", ans);
        }
    }

    public static void main(String[] args) {
        List<String> list = new Q22_GenerateParentheses().generateParenthesis(3);
        for(String str :list){
            System.out.println(str);
        }
    }
}
